package zuoshen_mid.class1.skill3_dataPreprocess;

import org.junit.Test;

/* 
    根据一个N*N的正方形中确定的最大边长全为1的正方形
*/
public class IncludingSquares {

    public int maxSquare1(int[][] nums) {
        int m = nums.length, n = nums[1].length, res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[i][j] == 0) continue;
                // 查找当前位置可以达到的最远的正方形
                int row = m - i;// 宽度
                int col = n - j;

                int k = Math.min(row, col);
                /*
                 * 遍历以（i + l, j + l) 为右下顶点的正方形是否满足条件
                 */
                for (int l = 1; l < k; l++) {
                    for (int a = i; a <= i + l; a++) {
                        if (nums[a][j] == 0)
                            continue;
                    }
                    for (int a = j; a <= j + l; a++) {
                        if (nums[i][a] == 0)
                            continue;
                    }
                    for (int a = i; a <= i + l; a++) {
                        if (nums[a][j + l] == 0)
                            continue;
                    }
                    for (int a = j; a <= j + l; a++) {
                        if (nums[i + l][a] == 0)
                            continue;
                    }
                    /*
                     * 通过四次检查，就是正方形
                     */
                    res = Math.max(res, l + 1);
                }
            }
        }
        return res;
    }

    public int maxSquare(int[][] nums) {
        int m = nums.length, n = nums[1].length, res = 0;

        int[][] f = new int[m][n];
        int[][] r = new int[m][n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (i == m - 1) {
                    f[i][j] = nums[i][j] == 1 ? 1 : 0;
                } else {
                    if (nums[i][j] == 0)
                        f[i][j] = 0;
                    else
                        f[i][j] = f[i + 1][j] + 1;
                }
            }
        }

        for (int j = n - 1; j >= 0; j--) {
            for (int i = 0; i < m; i++) {
                if (j == n - 1) {
                    r[i][j] = nums[i][j] == 1 ? 1 : 0;
                } else {
                    if (nums[i][j] == 0)
                        r[i][j] = 0;
                    else
                        r[i][j] = r[i][j + 1] + 1;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (f[i][j] == 0) 
                    continue;
                // 查找当前位置可以达到的最远的正方形
                int row = m - i;// 宽度
                int col = n - j;

                int k = Math.min(row, col);
                /*
                 * 遍历以（i + l, j + l) 为右下顶点的正方形是否满足条件
                 */
                for (int l = 1; l < k; l++) {
                    if (f[i][j] < l + 1) continue;
                    if (r[i][j] < l + 1) continue;
                    if (f[i][j + l] < l + 1) continue;
                    if (r[i + l][j] < l + 1) continue;
                    /*
                     * 通过四次检查，就是正方形
                     */
                    res = Math.max(res, l + 1);
                }
            }
        }
        return res;

       /*  switch(t) {
            case '+':
                nums.push(b + a);
                break;
            case '-':
                nums.push(b - a);
                break;
            case '*':
                nums.push(b - a);
                break;
            case '/':
                if (a == 0) {
                    exit(1);
                }
                nums.push(b / a);
        }  */
    }

    @Test
    public void test() {
        int[][] nums = new int[3][4];
        nums[0] = new int[]{0, 1, 1, 1};
        nums[1] = new int[]{0, 1, 0, 1};
        nums[2] = new int[]{0, 1, 1, 1};

        int res = maxSquare(nums);
        System.out.println(res);
    }
}
